package Hot100.Medium.String_2Pointer.DoublePointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC15_ThreeSum {

    public List<List<Integer>> threeSum(int[] nums){
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break; // 剪枝：如果最小的数都 >0，三个数和一定 >0
            if(k > 0 && nums[k] == nums[k - 1]) continue; // 去重：跳过相同起点

            int i = k + 1;// 左指针
            int j = nums.length - 1; // 右指针
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];

                if (sum < 0) {
                    // 左指针右移并跳过重复值
                    while(++i < j && nums[i] == nums[i -1]);
                } else if (sum > 0) {
                    while (i < --j && nums[j] == nums[j + 1]);
                } else {
                    // 找到一个三元组
                    res.add(Arrays.asList(nums[k], nums[i], nums[j]));
                    // 左指针右移并跳过重复值
                    while(++i < j && nums[i] == nums[i -1]);
                    // 右指针左移并跳过重复值
                    while (i < --j && nums[j] == nums[j + 1]);
                }
            }
        }
        return res;
    }
}
